// 29 两数相除
// https://leetcode.cn/problems/divide-two-integers/description/
// 思路
// 通过加法实现乘法
// 通过 >> 1 实现 /2的操作，这个是允许的
// 边界情况判断
// 其他
//

// dividend->被除数 divisor->除数 dividend/divisor

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
    const MAX_VALUE = 2 ** 31 - 1;
    const MIN_VALUE = -(2 ** 31);
    if (dividend > MAX_VALUE) dividend = MAX_VALUE;
    if (dividend < MIN_VALUE) dividend = MIN_VALUE;

    if (divisor > MAX_VALUE) divisor = MAX_VALUE;
    if (divisor < MIN_VALUE) divisor = MIN_VALUE;

    let negD1 = dividend < 0 ? dividend : 0 - dividend;
    let negD2 = divisor < 0 ? divisor : 0 - divisor;
    if (negD1 > negD2) return 0;

    if (dividend === divisor) return 1;
    if (Math.abs(dividend) === Math.abs(divisor)) return -1;
    if (divisor === 1) return dividend;

    if (divisor === -1) {
        if (dividend == MIN_VALUE) return MAX_VALUE;
        else return 0 - dividend;
    }

    if (dividend === 0) return 0;

    let res = simulateDivide(dividend, divisor);
    // console.log(`res = ${res}`);
    return res;
};

function simulateDivide(dividend, divisor) {
    let center = Math.abs(dividend);
    let left = 0;
    let right = Math.abs(dividend);

    let strBinDiv = Math.abs(divisor).toString(2);
    let len = strBinDiv.length - 1;
    while (len > 0) {
        if (strBinDiv[len] == '1') {
            right = right >> 1;
        }
        len--;
    }

    center = Math.abs((left + right) >> 1);

    if (center === 0) return 0;

    // console.log(`center is ${center}`);
    let res = add(divisor, center, dividend);
    // let loopMax = 10;
    while (res !== 0) {
        if (res == 1) {
            // center = Math.abs(center >> 1);
            right = center - 1;
        } else {
            left = center + 1;
            // center = Math.abs(center + ((Math.abs(dividend) - center) >> 1));
        }

        center = Math.abs((left + right) >> 1);

        res = add(divisor, center, dividend);
        console.log(
            `new center ${center} ${
                res == 0 ? 'yes' : res == 1 ? 'big' : 'small'
            }`
        );
        // loopMax--;
        // if (loopMax <= 0) break;
    }

    if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
        if (center == -(2 ** 31)) center = 2 ** 31 - 1;
        else center = 0 - center;
    }
    return center;
}

function multiply(x, y) {
    let result = 0;
    const MAX_VALUE = 2 ** 31 - 1;
    const MIN_VALUE = -(2 ** 31);

    let xIsNeg = x < 0;

    if (y === 311885) {
        console.log('fuck');
    }

    while (y > 0) {
        // 如果y是奇数，则将x加到结果中
        if (y & 1) {
            result += x;
            if (result <= MIN_VALUE) throw new Error('too small');
            if (result >= MAX_VALUE) throw new Error('too big');
        }
        // 将x左移一位（相当于乘以2）
        x <<= 1;
        if (xIsNeg && x > 0) {
            // return MIN_VALUE;
            throw new Error('too small');
        }

        // 将y右移一位（相当于除以2）
        y >>= 1;
    }
    return result;
}

function add(num, times, target) {
    const MAX_VALUE = 2 ** 31 - 1;
    const MIN_VALUE = -(2 ** 31);

    if (times === 0) {
        if (num == target) return 0;

        let extra = 0;
        if (target > 0) {
            // 比如 target:7 num:3 times3过大 times为2正好
            extra = Math.abs(target) - Math.abs(num);
        } else {
            // target -7 num: -3 times3小了 times2正好
            extra = Math.abs(num) - Math.abs(target);
        }

        if (extra >= 0 && Math.abs(num) > extra) {
            return 0;
        } else {
            return Math.abs(target) < Math.abs(num) ? 1 : -1;
        }
    }

    if (times == 311885) {
        console.log('fuck');
    }

    let time = 1;
    try {
        let base = multiply(num, times);
        if (
            (base == MIN_VALUE || base == MAX_VALUE) &&
            target < MAX_VALUE &&
            target > MIN_VALUE
        ) {
            return 1;
        }

        let extra = 0;
        if (target > 0) {
            // 比如 target:7 num:3 times3过大 times为2正好
            extra = Math.abs(target) - Math.abs(base);
        } else {
            // target -7 num: -3 times3小了 times2正好
            extra = Math.abs(target) - Math.abs(base);
        }

        if (extra >= 0 && Math.abs(num) > extra) {
            return 0;
        } else {
            return Math.abs(target) < Math.abs(base) ? 1 : -1;
        }
    } catch (ex) {
        if (ex.message == 'too big') {
            return 1;
        }

        if (ex.message == 'too small') {
            return -1;
        }
    }
}

function logD(dividend, divisor) {
    let res = divide(dividend, divisor);
    console.log(`${dividend} / ${divisor} = ${res}`);
}

// logD(10, 3);
// logD(10, 2);
// logD(7, -3);
// logD(1, 1);
// logD(1, -1);
// logD(-10, 3);
// logD(-10, -3);
// logD(0, -3);
// logD(-2147483648, -1); // 2147483647
logD(-2147483648, 2); // -1073741824
// logD(2147483647, 3); // 715827882.3333334
// logD(1, 2);
// logD(1004958205, -2137325331); // 0
// logD(-1021989372, -82778243); // 12
